/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import junit.framework.TestCase.assertEquals
import org.jheaps.AddressableHeap
import org.jheaps.array.BinaryArrayAddressableHeap
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

class AddressableHeapsRandomTest {
    @Test
    fun test() {
        test(Random())
    }

    @Test
    fun testSeed13() {
        test(Random(13))
    }

    @Test
    fun testSeed37() {
        test(Random(37))
    }

    @Test
    fun testRandomDeletesSeed37() {
        testRandomDeletes(37)
    }

    @Test
    fun testRandomDelete() {
        testRandomDeletes(Random().nextLong())
    }

    private fun test(rng: Random) {
        val classes = 8

        val h = java.lang.reflect.Array.newInstance(
            AddressableHeap::class.java,
            classes
        ) as Array<AddressableHeap<Int, Void>>
        h[0] = PairingHeap()
        h[1] = BinaryTreeAddressableHeap()
        h[2] = FibonacciHeap()
        h[3] = BinaryArrayAddressableHeap()
        h[4] = CostlessMeldPairingHeap()
        h[5] = SkewHeap()
        h[6] = ReflectedPairingHeap()
        h[7] = LeftistHeap()

        val s = java.lang.reflect.Array.newInstance(
            MutableList::class.java, classes
        ) as Array<MutableList<AddressableHeap.Handle<Int, Void>>>
        for (j in 0 until classes) {
            s[j] = ArrayList()
        }

        for (i in 0 until SIZE) {
            val k = rng.nextInt()
            for (j in 0 until classes) {
                s[j].add(h[j].insert(k, null))
            }
            for (j in 1 until classes) {
                assertEquals(h[0].findMin().key, h[j].findMin().key)
            }
        }

        for (i in 0..4) {
            val it = java.lang.reflect.Array.newInstance(
                MutableIterator::class.java,
                classes
            ) as Array<Iterator<AddressableHeap.Handle<Int, Void>>>
            for (j in 0 until classes) {
                it[j] = s[j].iterator()
            }

            while (true) {
                var shouldStop = false
                for (j in 0 until classes) {
                    if (!it[j].hasNext()) {
                        shouldStop = true
                        break
                    }
                }

                if (shouldStop) {
                    break
                }

                val handle = java.lang.reflect.Array.newInstance(
                    AddressableHeap.Handle::class.java, classes
                ) as Array<AddressableHeap.Handle<Int, Void>>
                for (j in 0 until classes) {
                    handle[j] = it[j].next()
                }
                val newKey = handle[0].key / 2
                if (newKey < handle[0].key) {
                    for (j in 0 until classes) {
                        handle[j].decreaseKey(newKey)
                    }
                }

                for (j in 1 until classes) {
                    assertEquals(h[0].findMin().key, h[j].findMin().key)
                }
            }
        }

        while (!h[0].isEmpty) {
            for (j in 1 until classes) {
                assertEquals(h[0].findMin().key, h[j].findMin().key)
            }
            for (j in 0 until classes) {
                h[j].deleteMin()
            }
        }
    }

    private fun testRandomDeletes(seed: Long) {
        val classes = 8

/*
        val h = java.lang.reflect.Array.newInstance(
            AddressableHeap::class.java,
            classes
        ) as Array<AddressableHeap<Int, Void>>
        h[0] = PairingHeap()
        h[1] = BinaryTreeAddressableHeap()
        h[2] = FibonacciHeap()
        h[3] = BinaryArrayAddressableHeap()
        h[4] = CostlessMeldPairingHeap()
        h[5] = SkewHeap()
        h[6] = ReflectedPairingHeap()
        h[7] = LeftistHeap()
*/

        val h =  arrayOf<AddressableHeap<Int, Void>>(PairingHeap()
                   ,BinaryTreeAddressableHeap()
                   ,FibonacciHeap()
                   ,BinaryArrayAddressableHeap()
                   ,CostlessMeldPairingHeap()
                   ,SkewHeap()
                   ,ReflectedPairingHeap()
                   ,LeftistHeap()
        )


        /*val s = java.lang.reflect.Array.newInstance(
            MutableList::class.java, classes
        ) as Array<MutableList<AddressableHeap.Handle<Int, Void>?>>
        for (i in 0 until classes) {
            s[i] = ArrayList()
        }*/
        val s = Array<MutableList<AddressableHeap.Handle<Int, Void>?>>(classes){ArrayList()}

        for (i in 0 until SIZE) {
            for (j in 0 until classes) {
                s[j].add(h[j].insert(i, null))
            }
            for (j in 1 until classes) {
                assertEquals(h[0].findMin().key, h[j].findMin().key)
            }
        }

        for (j in 0 until classes) {
            s[j].shuffle(Random(seed))
        }

        for (i in 0 until SIZE) {
            for (j in 1 until classes) {
                assertEquals(h[0].findMin().key, h[j].findMin().key)
            }
            for (j in 0 until classes) {
                s[j][i]!!.delete()
            }
        }

        for (j in 0 until classes) {
            Assert.assertTrue(h[j].isEmpty)
        }
    }

    companion object {
        private const val SIZE = 250000
    }
}
